import java.util.*;

class Solution {
    public static List<Integer> replaceNonCoprimes(int[] nums) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        List<Integer> res = new ArrayList<>();
        for (int num : nums) {
            if (stack.isEmpty() || gcd(num, stack.peek()) == 1) {
                stack.push(num);
            } else {
                int lcm = lcm(num, stack.peek());
                while (!stack.isEmpty() && gcd(stack.peek(), lcm) != 1 ) {
                    stack.pop();
                }
                stack.push(lcm);
            }
        }
        while (!stack.isEmpty()) {
            res.add(stack.pop());
        }
        Collections.reverse(res);
        return res;
    
    }
        


    private static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }

    private static int gcd(int a, int b) { 
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static void main(String[] args) {
        List<Integer> ans = replaceNonCoprimes(new int[]{1, 2, 3, 4, 5});
        System.out.println(ans);
    }
}